"""
https://leetcode.cn/problems/longest-valid-parentheses/description/

32. 最长有效括号
困难
相关标签
相关企业
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号
子串
的长度。

 

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：

输入：s = ""
输出：0
 

提示：

0 <= s.length <= 3 * 104
s[i] 为 '(' 或 ')'
"""

from typing import List


class Solution:
    """
    某个字符串有效的标记是：
    从最左侧开始遍历，同时维护一个标记数，初始值为0，
    出现(则记为+1,出现)则-1,
    整个过程如果没有任何时候标记数均不小于0，且最后标记数为0，
    则这个字符串就是有效的

    一个思路是，记录从每个索引开始的最大有效数，之后再取最大值
    (()
    1 1 -1
    1 2 1->0 (load first 1->1)
    1 0->2
    -1->0
    res=2

    )()())
    -1 1 -1 1 -1 -1
    -1->0 (next begin 1)
    1 0 1 0 -1->4 (next begin 6)
    -1->0
    res=4

    record sum

    """
    def longestValidParentheses(self, s: str) -> int:
        valid_count:List[int]=[0]*len(s)
        left=0
        min_left=0
        win_sum=0
        max_valid_count=0
        for i,ch in enumerate(s):
            if ch=='(':
                win_sum+=1
            else:
                win_sum-=1     
                # 维护max_valid_count
                if win_sum==0:
                    max_valid_count=max(max_valid_count,i-left+1)
                    min_left=i+1
                # 维护left
                elif win_sum<0:
                    win_sum=0
                    left=i+1 
                    min_left=left
            valid_count[i]=win_sum
        # 如果到最后，仍大于0
        if win_sum>0:
            while min_left<len(s):
                if valid_count[min_left]==win_sum:
                    max_valid_count=max(max_valid_count,len(s)-min_left-1)
                    break
                min_left+=1
        return max_valid_count

if __name__=='__main__':
    sol=Solution()
    params=[
        ('(()',2),
        (')()())',4),
        ('()(()',2),
        ('(()()',4),
        ('))))((()((',2),
    ]
    for s,ast in params:
        res=sol.longestValidParentheses(s)
        print(res,res==ast)

    """
    ()(()
    1 -1 1 1 -1
    1 0 1 2 1
    res=2

    (()()
    1 1 -1 1 -1
    1 2 1 2 1
    res=4

    ))))((()((
    -1 -1 -1 -1 1 1 1 -1 1 1
    4:1 2 3 2 3 4
    4 // 1
    4 5 // 2
    4 5 6 // 3
    4 5 6 // 2
    4 5 6 // 3
    4 5 6 9 // 4

    """

    pass